package com.huangpeng.algorithm.snowFlake;


/**
 * @Author huangpeng
 * @Title 在O(1)时间内删除链表结点。  给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间内删除该节点
 * @Package
 * @Date 2021/5/21 14:04
 * @Description
 * @Version 1.0
 */
public class DeleteNode {
    private int value;
    private DeleteNode next;

    public DeleteNode() {
    }

    public DeleteNode(int value, DeleteNode next) {
        this.value = value;
        this.next = next;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public DeleteNode getNext() {
        return next;
    }

    public void setNext(DeleteNode next) {
        this.next = next;
    }

    public static void main(String[] args) {
        DeleteNode head = new DeleteNode(10, null);
        DeleteNode tail = head;
        DeleteNode deleteNode = null;
        for (int i = 0; i < 10; i++) {
            DeleteNode node = new DeleteNode(i, null);
            tail.setNext(node);
            tail = node;
            if (i == 5) {// 删除链表中某个结点
                deleteNode = node;
            }
        }
        deleteNode = tail;// 删除链表中的尾结点
        head = head.getNext();
        forwardPrint(head);
        delete(head, deleteNode);
        forwardPrint(head);
    }

    public static void forwardPrint(DeleteNode head) {
        DeleteNode node = head;
        while (node != null) {
            System.out.print(node.getValue() + "->");
            node = node.getNext();
        }
        System.out.println();
    }

    public static void delete(DeleteNode head, DeleteNode deleteNode) {
        if (head == null || deleteNode == null) {
            return;
        }
        if (deleteNode.getNext() != null) {// 删除链表中的一个结点
            DeleteNode next = deleteNode.getNext();
            deleteNode.setValue(next.getValue());
            deleteNode.setNext(next.getNext());
            next = null;
        } else if (head == deleteNode) {// 链表只有一个头结点的删除
            head = deleteNode = null;
        } else {// 链表有多个结点，删除尾结点
            DeleteNode node = head;
            while (node.getNext() != deleteNode) {
                node = node.getNext();
            }
            node.setNext(null);
            deleteNode = null;
        }
    }
}

